一、PATCHY-SAN [2016]

《Learning Convolutional Neural Networks for Graphs》

1. 论文 《Learning Convolutional Neural Networks for Graphs》 的目标是：让卷积神经网络能够解决一大类 graph-based 的学习问题。我们考虑以下两个问题：

   • 给定 graph 的一个集合，学习一个函数，该函数可用于针对 unseen graph 的分类问题或回归问题。任意两个graph之间的结构不一定是相同的。例如，graph集合中每个graph都可以建模一种化合物，输出可以是一个函数从而将 unseen 的化合物映射到它们对癌细胞活性抑制的 level 。

   • 给定一个大型的graph，学习graph 的 representation，该 representation 可用于推断 unseen 的图属性（如节点类型、或missing edge）。

   该论文提出了一个用于有向图或无向图的 learning representation 框架。graph 可能具有离散属性或连续属性的节点和边（甚至有多个属性），并且可能具有多种类型的边。类似于图像的卷积神经网络，论文从输入图 input graph 构建局部连接（locally connected）的邻域。这些邻域是有效生成的，并且作为卷积架构的感受野（receptive field），从而允许框架学习有效的 graph representation 。

   所提出的方法建立在用于图像的卷积神经网络的概念之上，并将卷积神经网络扩展到任意的graph 。下图说明了用于图像的 CNN 的局部连接感受野。如下图所示，黑色/白色节点表示不同的像素值（黑色像素值为1、白色像素值为0 ），红色节点表示当前卷积核的中心位置。(a) 图给出了一个 3x3 卷积核在一个 4x4 图像上的卷积过程，其中步幅为1、采用非零填充。图像可以表示为正方形的网格图 square grid graph ，其节点代表像素。现在，可以将 CNN 视为遍历节点序列（如下图(a)中的节点 1,2,3,4），并为每个节点生成固定大小的邻域子图（ neighborhood subgraph ）（如下图 (b) 中的 3x3 网格）。邻域子图用作感受野从而读取像素值。由于像素的隐式空间顺序 （implicit spatial order），节点序列（如下图 (a) 中的节点 1,2,3,4）从左到右、从上到下是唯一确定的。对于 NLP 问题也是如此，其中每个句子（及其解析树 parse-tree）确定了单词序列。然而，对于许多graph 集合，缺少特定于问题的顺序（ problem-specific ordering）（空间的、时间的、或其它的顺序），并且graph 的节点不存在对应关系（即，两个graph 之间的结构不相等）。在这种情况下，必须解决两个问题：

   • 确定节点序列，其中我们要对序列中的节点创建邻域子图。

   • 计算邻域子图的归一化，即从graph 到排序空间的唯一映射（unique mapping） 。

     子图的归一化指的是对子图节点进行某种特定顺序的排序。

   

   所提出的方法，称作 PATCHY-SAN，解决了任意graph 的这两个问题：

   • 对于每个输入graph ，PATCHY-SAN 首先确定需要创建邻域子图的节点（及其访问顺序）。

   • 对于这些节点中的每一个，PATCHY-SAN 抽取和归一化一个刚好由 $k$$k$ 个节点组成的邻域子图，即该邻域子图被唯一地映射到具有固定线性顺序（fixed linear order）的空间。归一化的邻域子图用作所考虑节点的感受野。

   • 最后，feature learning 组件（如卷积层、稠密层）与归一化的邻域子图（作为 CNN 的感受野）相结合。

   下图说明了 PATCHY-SAN 的架构，其中红色节点表示节点序列中的节点，邻域子图大小 $k=5$$k=5$ 。

   

   PATCHY-SAN 与现有方法相比具有几个优点：

   • 首先，它高效、可并行化，并且适用于大型graph 。

   • 其次，对于很多application（从计算生物学到社交网络分析），可视化学到的网络主题（ network motif ）很重要。PATCHY-SAN 支持特征可视化（feature visualization），从而提供对图结构属性 （ structural property ）的洞察。

   • 第三，PATCHY-SAN 无需制作另一个 graph kernel，而是学习 application dependent 的特征而无需进行特征工程。

   论文的理论贡献是：

   • 定义graph 上的归一化问题（ normalization problem ），以及该问题的复杂度。

   • 一种用于graph 集合的方法，该方法对比了 graph labeling 方法。

   • 实验结果表明，PATCHY-SAN 推广了用于图像的 CNN。在标准的 benchmark 数据集上，论文证明与 SOTA 的 graph kernel 相比，学到的用于graph的 CNN 既高效（efficient）又有效（ effective）。

2. 相关工作：

   • graph kernel：graph kernel 允许kernel-based 的学习方法，如直接在graph 上工作的 SVM 。graph 上的 kernel 最初被定义为single graph 上的节点的相似度函数（ similarity function）。两类具有代表性的 kernel 是skew spectrum kernel 和 kernel based on graphlet 。后者与我们的工作有关，因为它基于固定大小的子图来构建 kernel 。这些子图，通常被称作 motif 或 graphlet，反映了功能性的网络的属性（ functional network property ）。然而，由于子图枚举（subgraph enumeration）的组合复杂性（ combinatorial complexity），graphlet kernel 仅限于具有少量节点的子图。

     Weisfeiler-Lehman (WL) kernel 是一类有效的 graph kenerl 。然而，WL kernel 仅支持离散特征，并且在测试阶段使用与训练样本数量成线性关系的内存（而不是与测试样本数量成线性关系）。PATCHY-SAN 使用 WL 作为一种可能的 labeling 过程来计算感受野。

     deep graph kernel 和 graph invariant kernel 根据诸如最短路径（shortest path）、graphlet、子树（subtree）、以及其它的图不变量 （graph invariant）等小型子结构的存在或数量来比较图 （compare graph ）。相反，PATCHY-SAN 从graph 数据中学习子结构，并且不限于预定义 （predefined）的一组主题（motif）。

     此外，所有 graph kernel 的训练复杂度至少是graph 数量的二次方关系，这对于大型graph 而言是不可行的，但是 PATCHY-SAN 的训练复杂度是graph 数量的线性关系。

   • graph neural network: GNN ：GNN 是图上定义的循环神经网络（recurrent neural network: RNN）架构。GNN 将循环神经网络应用于图结构上的游走（walk），传播 node representation，直到达到一个不动点 （fixed point） 。然后将生成的 node representation 用作分类和回归问题中的特征。GNN 仅支持离散特征，并在每次学习迭代过程中执行与图的边和节点数量一样多的反向传播操作。

     注：GNN 理论上也支持连续特征。

     Gated Graph Sequence Neural Network: GGSNN 修改 GNN 以使用门控循环单元（gated recurrent unit: GRU）并输出序列。

   • 最近的工作将 CNN 扩展到不同于低维网格结构的拓扑。然而，所有这些方法都假设一个全局的图结构，即，跨graph 的节点的对应关系（correspondence）。

     《Convolutional networks on graphs for learning molecular fingerprints》 对graph 执行卷积类型的操作，开发了一个 specific graph feature 的可微变体（differentiable variant）。

1.1 基础概念

1.1.1 CNN

1. CNN 受到早期工作的启发，该工作表明：动物的视觉皮层包含复杂的细胞排列，它们负责检测视野（ visual field ）的小局部区域（small local region）中的光。CNN 是在 1980 年代开发的，并已应用于图像、语音、文本、以及药物发现问题。CNN 的前身是 Neocognitron。典型的 CNN 由卷积层、稠密层（dense layer）组成。第一个卷积层的目的是提取在输入图像的局部区域内发现的常见模式。CNN 对输入图像利用学到的 filter 执行卷积运算，并将卷积结果输出为张量，输出的 depth 是 filter 的数量。

1.1.2 Graph Kernel（读者补充）

1. 目前现有的大多数 Graph Kernel 算法都是基于 R-Convolution 理论构建而来，其理论思想是：设计一种图的分解算法，两个图的核函数和图分解后的子结构的相似程度有关。

   给定两个图 $G_1(V_1,E_1),G_2(V_2,E_2)$$G_1(V_1,E_1),G_2(V_2,E_2)$ 以及一种图的分解方式 $\mathcal{F}(\cdot )$$\mathcal F(\cdot)$，则分解后的子结构为：

   $$\begin{array}{c}\mathcal{F}(G_1)=\{S_{1,1},S_{1,2},\cdots ,S_{1,n_1}\}\\ \mathcal{F}(G_2)=\{S_{2,1},S_{2,2},\cdots ,S_{2,n_2}\}\end{array}$$

   基于该子结构，则 $G_1$$G_1$ 和 $G_2$$G_2$ 的核函数可以表示为：

   $$k_R(G_1,G_2)=\sum _{i=1}^{n_1}\sum _{j=1}^{n_2}\delta (S_{1,i},S_{2,j})$$

   其中：

   $$\begin{array}{c}\delta (S_a,S_b)=\{\begin{array}{ll}1,& S_a\text{同构}{S}_b\\ 0,& \text{else}\end{array}\end{array}$$

   因此，任意一种图的分解方式 $\mathcal{F}(\cdot )$$\mathcal F(\cdot)$ 以及任意一种子结构同构判断方式 $\delta (\cdot )$$\delta(\cdot)$ 的组合都可以定义一种新的 Graph Kernel ，常见的主要分为三类：

   • 基于游走的Graph Kernel，如 Random Walk Kernel。

   • 基于路径的 Graph Kernel，如 Shortest-Path Kernel 。

   • 基于子树（subtree） 或者子图 （subgraph）的 Graph Kernel ，如 Weisfeiler-Lehman Subtree Kernel。

   另外，除了 R-Convolution 系列之外，还有其它的 Graph Kernel 。

2. Random Walk Kernel：随机游走Kernel 的基本思想是：统计两个输入图中相同的随机游走序列的数量。

   给定输入图 $G_1(V_1,E_1),G_2(V_2,E_2)$$G_1(V_1,E_1),G_2(V_2,E_2)$，设节点 $v$$v$ 的label 为 $l_v$$l_v$ 。定义direct product graph $G_{\times }$$G_{\times}$ 为： $G_{\times }=(V_{\times },E_{\times })$$G_{\times} = (V_{\times},E_{\times})$ ，其中：

   $$\begin{array}{c}{V}_{\times }(G_1\times G_2)=\{(v_1,w_1)\in V_1\times V_2\}\mid l_{v_1}=l_{w_1}\}\\ E_{\times }(G_1\times G_2)=\{((v_1,w_1),(v_2,w_2))\in V_{\times }\times V_{\times }\mid (v_1,v_2)\in E_1,\\ (w_1,w_2)\in E_2,l_{(v_1,v_2)}=l_{(w_1,w_2)}\}\end{array}$$

   其中：

   • $l_v$$l_v$ 表示节点 $v$$v$ 的label， $l_{(v_1,v_2)}$$l_{(v_1,v_2)}$ 表示边 $(v_1,v_2)$$(v_1,v_2)$ 的 label 。注意，这里的 label 其实是属性，而不是监督学习中的监督信号。

   • $V_{\times }$$V_\times$ 表示图 $G_1,G_2$$G_1,G_2$ 中相同 label 的节点组成的 pair 对。

   • $E_{\times }$$E_\times$ 表示图 $G_1,G_2$$G_1,G_2$ 中相同 label 的边组成的 pair 对，且边的对应节点的 label 分别相同。

   在 $G_{\times }$$G_\times$ 中，每个节点其实代表两个子节点，这两个子节点在各自图中具有相同的 label。$G_{\times }$$G_\times$ 中的边代表：

   • 起点背后的两个子节点，在各自图中具有相同的 label。

   • 终点背后的两个子节点，在各自图中具有相同的 label。

   • 起点和终点背后的两对子边，在各自图中具有相同的 label。

   定义图 $G_{\times }$$G_{\times}$ 的邻接矩阵为 ${\mathbf{A}}_{\times }$$\mathbf A_{\times}$ ，则随机游走 kernel 定义为：

   $$k_{\times }(G_1,G_2)=\sum _{i,j=1}^{|V_{\times }|}{\left[\sum _{n=0}^{\mathrm{\infty }}{\lambda }_n{\mathbf{A}}_{\times }^n\right]}_{i,j}$$

   其中 ${\lambda }_n$$\lambda_n$ 必须仔细挑选从而保证 $k_{\times }$$k_\times$ 的收敛性。

   $\sum _{i,j=1}^{|V_{\times }|}{\left[{\mathbf{A}}_{\times }^n\right]}_{i,j}$$\sum_{i,j=1}^{|V_{\times}|}\left[ \mathbf A^n_{\times}\right]_{i,j}$ ：给出了图 $G_1$$G_1$ 和 $G_2$$G_2$ 中，长度为 $n$$n$ 的、特定条件的路径的数量，该路径满足以下条件：路径的节点label 序列完全相同、路径的边label 序列完全相同。

3. Shortest-Path Kernel：最短路径 Kernel 的基本思想是：统计两个输入图中相同标签之间的最短路径。

   给定输入图 $G_1(V_1,E_1),G_2(V_2,E_2)$$G_1(V_1,E_1),G_2(V_2,E_2)$：

   • 首先通过Floyd 成对最短路径生成算法，构建每个图的节点之间的最短路径，得到新的图 $G_1^F(V_1,E_1^F),G_2^F(V_2,E_2^F)$$G_1^F\left(V_1,E_1^F\right),G_2^F\left(V_2,E_2^F\right)$ ，其中 $E_1^F$$E_1^F$ 给出了 $V_1$$V_1$ 的两两节点之间最短路径、$E_2^F$$E_2^F$ 给出了 $V_2$$V_2$ 的两两节点之间最短路径。

   • 计算：

     $$k_{shortest-path}(G_1,G_2)=\sum _{e_1\in E_1^F}\sum _{e_2\in E_2^F}{k}_{walk}^{(1)}(e_1,e_2)$$

     其中 $k_{walk}^{(1)}$$k_{walk}^{(1)}$ 为一个定义在长度为1 的 edge walk 上的正定核。

4. Weisfeiler-Lehman Subtree Kernel ：它基于 Weisfeiler-Lehman 算法。

   • 节点 label 更新：对于图 $G$$G$ 的节点 $v$$v$ ，获取节点 $v$$v$ 的邻域节点集合 ${\mathcal{N}}_v$$\mathcal N_v$，通过一个 hash 函数得到节点 $v$$v$ 的新label：

     $$l_v\leftarrow \text{hash}(l_v,l_{{\mathcal{N}}_v})$$

     其中 $l_v$$l_v$ 为节点 $v$$v$ 的 label，$l_{{\mathcal{N}}_v}$$l_{\mathcal N_v}$ 为邻域节点集合${\mathcal{N}}_v$$\mathcal N_v$ 的 label 集合。

     更新后的新label 包含了其直接邻域的节点信息。因此如果两个节点更新后的 label 相同，我们可以认为其邻域结构是同构的。

   • 更新图的所有节点 、重复更新最多 $K$$K$ 轮直到收敛，最终得到图 $G^{\prime }$$G^\prime$ 。

     每一轮更新后，节点 $v$$v$ 的 label 就包含了更大规模的邻域的节点信息，最终每个节点的 label 编码了图的全局结构信息。

   • 对于输入图 $G_1,G_2$$G_1,G_2$ 我们分别对其执行 Weisfeiler-Lehman 算法，最终根据 $G_1^{\prime },G_2^{\prime }$$G^\prime_1,G_2^\prime$ 的 节点label 集合的相似性（如 Jaccard 相似性）来得到核函数：

     $$k_{WL}(G_1,G_2)=\frac{|l_{V_1}\bigcap l_{V_2}|}{|l_{V_1}\bigcup l_{V_2}|}$$

     其中 $l_V$$l_{V}$ 为所有节点的label 集合。

5. 一旦定义了 Graph Kernel，则我们可以使用基于核技巧的方法，如 SVM 来直接应用在图上。

1.2 模型

1. 给定图 $G=(V,E)$$G=(V,E)$，$V=\{v_1,\cdots ,v_n\}$$V=\{v_1,\cdots,v_n\}$ 为节点集合，$E\subseteq V\times V$$E\sube V\times V$ 为边集合。假设节点数量为 $|V|=n$$|V|=n$ ，边的数量 $|E|=m$$|E|=m$ 。

   • 定义图的邻接矩阵 $\mathbf{A}\in {\mathbb{R}}^{n\times n}$$\mathbf A\in \mathbb R^{n\times n}$ 为：

     $$\begin{array}{c}{A}_{i,j}=\{\begin{array}{ll}1,& (v_i,v_j)\in E\\ 0,& \text{else}\end{array}\end{array}$$

   • 每个节点以及每条边可以包含一组属性，这些属性可以为离散的，也可以为连续的。这里我们用 “属性” 而不是 “标签” 来避免概念的混淆。

   • 定义一个游走序列 walk 是由连续的边组成的一个节点序列。定义一条路径（ path ）是由不重复节点构成的walk 。

   • 定义 $d(u,v)$$d(u,v)$ 为节点 $u$$u$ 和 $v$$v$ 之间的距离，它是 $u$$u$ 和 $v$$v$ 之间的最短路径距离。

   • 定义 ${\mathcal{N}}_1(v)$$\mathcal N_1(v)$ 为节点 $v$$v$ 的一阶邻域节点集合，它由与 $v$$v$ 直连的所有节点构成。

2. Labeling and Node Partitions：PATCHY-SAN 利用了graph labeling 对节点进行排序。

   • graph labeling：如果图的节点自带label， 则我们可以直接用该label 。如果节点没有label ，则我们可以通过一个graph labeling 函数 $F_l:V\to S$$F_l: V\rightarrow S$ 为图注入label ，其中 $S$$S$ 为一个有序集（如，实数集 $\mathbb{R}$$\mathbb R$ 或整数集 $\mathbb{Z}$$\mathbb Z$）。 graph labeling 过程计算输入图中节点的 label。

     graph labeling 的例子包括：通过节点的度（degree ）计算label、通过节点的中介中心性（between centrality ）计算 label 。一个节点 $v$$v$ 的中介中心性为：网络中经过节点 $v$$v$ 的最短路径占所有最短路径的比例。

   • ranking：一个排序（ ranking ）（或者染色 coloring ）是一个函数 $F_r:V\to \{1,2,\cdots ,|V|\}$$F_r: V\rightarrow \{1,2,\cdots,|V|\}$ 。每个graph labeling 引入一个排序函数，使得当且仅当 $F_l(u)>F_l(v)$$F_l(u)\gt F_l(v)$ 时有 $F_r(u)<F_r(v)$$F_r(u)\lt F_r(v)$ ，即：label 越大则排名越靠前。如果图 $G$$G$ 的 labeling $F_l$$F_l$ 是单射函数，则它确定 $G$$G$ 的节点的全体顺序。根据该顺序我们定义一个邻接矩阵 ${\mathbf{A}}^l(G)$$\mathbf A^l(G)$，它定义为：

     $$\begin{array}{c}{\mathbf{A}}^l(G)=\begin{array}{clrcccc}& r_1& r_2& r_3& r_4& \cdots & r_n\\ v_1:F_r(v_1)=1& 1& 0& 0& 0& \cdots & 0\\ v_2:F_r(v_2)=4& 0& 0& 0& 1& \cdots & 0\\ v_3:F_r(v_3)=3& 0& 0& 1& 0& \cdots & 0\\ v_4:F_r(v_4)=2& 0& 1& 0& 0& \cdots & 0\\ ⋮& ⋮& ⋮& ⋮& ⋮& \ddots & ⋮\\ v_n:F_r(v_n)=n& 0& 0& 0& 0& \cdots & 1\end{array}\end{array}$$

     其中节点 $v$$v$ 在 ${\mathbf{A}}^l(G)$$\mathbf A^l(G)$ 中的位置由它的排名 $F_r(v)$$F_r(v)$ 决定。

     行代表节点，列代表排名。

   • 划分（ partition）：graph labeling 引入节点集合 $V$$V$ 的一个划分：$\{V_1,\cdots ,V_K\}$$\{V_1,\cdots,V_K\}$ ，其中 $K$$K$ 为label 的取值类别数。节点 $u,v\in V_i$$u,v\in V_i$ 当且仅当 $F_l(u)=F_l(v)$$F_l(u) = F_l(v)$ 。

     Weisfeiler-Lehman 算法是一种划分图节点的过程，它也被称作 color refinement 和 naive vertex classification 。该算法在机器学习社区中引起了相当广泛的兴趣，因为它可以应用于图模型的加速推断、以及作为一种计算 graph kernel 的方法。

3. PATCHY-SAN 使用这些 graph labeling 过程来对图的节点施加顺序，从而替代缺失的、application-dependent 的顺序（如时间顺序，空间顺序）。

4. 同构和规范化（Isomorphism and Canonicalization）：在很多应用领域存在的一个计算问题是：确定两个图是否是同构曲面。图同构问题（ graph isomorphism (GI) problem ）是 NP 的，但是不知道是属于 P 还是 NP-hard 。在一些温和的限制下，图同构问题是 P 的，例如对于有界 degree 的图。

   图 $G$$G$ 的规范化是具有固定节点顺序的图 $G^{\prime }$$G^\prime$，它与 $G$$G$ 同构并且表达了 $G$$G$ 的整个同构族（isomorphism class）。在实践中，图规范化工具 NAUTY 表现出了卓越的性能。

5. 当 CNN 应用于图像时，感受野（正方形网格）以特定的步长在图像上移动。感受野为每个通道读取一次像素值，并为每个通道创建一批数值。由于图像的像素具有隐式排列（即，空间顺序），因此感受野总是从左到右、从上到下移动。此外，空间顺序唯一地确定了每个感受野的节点以及这些节点映射到排序空间方式。因此，当且仅当像素的结构角色 （structural role）（它们在感受野内的空间位置）相同时，使用两个不同绝对位置的感受野读取到的两个像素值被分配到同一个相对位置。

   为了展示 CNN 和 PATCHY-SAN 之间的联系，我们把图像上的 CNN 视为一种框架：首先识别正方形网格图（代表图像）中的节点序列，然后为该序列中的每个节点建立一个归一化的邻域子图（neighborhood graph）（即，感受野）。

   对于缺少 application-dependent 节点顺序并且任何两个图的节点尚未对齐的图集合，我们需要为每个图确定：

   • 一个节点序列，其中我们即将为序列中的每个节点创建邻域子图。

   • 从图结构到向量 representation 的唯一映射，使得相似的邻域子图具有相似的向量representation 。

   我们通过graph labeling 过程来解决这些问题。如果来自两个不同图的节点在图中的结构角色相似，那么它们被分配到各自邻接矩阵中的相似的相对位置。给定一组图，PATCHY-SAN 对每个图执行以下操作：

   • 采用 Node Sequence Selection 算法从图中选择一个固定长度的节点序列。

   • 采用 Neighborhood Assembly 算法为节点序列中的每个节点组装一个固定大小的邻域。

   • 通过 Graph Normalization 对每个邻域子图进行归一化处理，从而将无序的图转换为有序的、长度固定的节点序列。

   • 利用CNN 学习邻域的 representation。

1.2.1 Node Sequence Selection

1. 节点序列选择node sequence selection是为每个输入图识别需要创建感受野的节点序列的过程。

   • 首先，输入图的节点根据给定的 graph labeling 进行排序。

   • 其次，使用给定的步幅 $s$$s$ 遍历生成的节点序列，并对每个访问到的节点采用创建感受野的算法来构造一个感受野，直到恰好创建了 $w$$w$ 个感受野为止。

     $w$$w$ 决定了卷积运算输出 feature map 的尺寸，它对应于一维CNN 中的序列长度。

   步幅 $s$$s$ 决定了在节点序列中，需要创建感受野的两个节点之间的距离。如果节点数量小于 $w$$w$ ，则算法创建全零的感受野，用于填充。也可以采用其它节点序列选择方法，如根据 graph labeling 进行深度优先遍历。

   类比一维卷积的运算，那么 $w$$w$ 就是数据序列的长度，$s$$s$ 就是一维卷积的步长。每个输入图都需要对其到 $w$$w$ 个感受野（即一维卷积中的序列长度对齐）。

2. Select Node Sequence 算法：

   • 算法输入：

     • graph labeling 函数 $F_l(\cdot )$$F_l(\cdot)$

     • 输入图 $G=(V,E)$$G=(V,E)$

     • 步幅 $s$$s$ 、宽度 $w$$w$ 、感受野尺寸 $k$$k$

   • 算法输出：被选择的节点序列，以及对应的感受野

   • 算法步骤：

     • 根据 $F_l(\cdot )$$F_l(\cdot)$ 选择节点集合 $V$$V$ 中的 top $w$$w$ 个节点，记作 $V_{\text{sort}}$$V_\text{sort}$ 。

     • 初始化： $i=1,j=1$$i=1,j=1$ 。

     • 迭代，直到 $j\ge w$$j\ge w$ 停止迭代。迭代步骤为：

       • 如果 $i\le |V_{\text{sort}}|$$i\le |V_\text{sort}|$，则对排序后的节点 $i$$i$ 创建感受野 $f=\text{CreateReceptiveField}(V_{\text{sort}}[i],k)$$f=\text{CreateReceptiveField}(V_\text{sort}[i],k)$ ；否则创建全零感受野 $f=\text{ZeroReceptiveField}(k)$$f=\text{ZeroReceptiveField}(k)$ 。

       • 将 $f$$f$ 应用到每个输入通道。

         因为节点的特征可能是一个向量，表示多维度属性。

       • 更新：$i=i+s,j=j+1$$i = i+s,\quad j=j+1$ 。

     • 返回访问到的节点序列，以及创建的感受野序列。

1.2.2 Neighborhood Assembly

1. 对于被选择的节点序列，必须为其中的每个节点构建一个感受野。创建感受野的算法首先调用邻域组装算法来构建一个局部邻域，邻域内的节点是感受野的候选节点。

   给定节点 $v$$v$ 和感受野的尺寸 $k$$k$ ，邻域组装算法首先执行广度优先搜索 BFS 来探索与节点 $v$$v$ 距离依次增加的节点，并将这些被探索到的节点添加到集合 ${\mathcal{N}}_v$$\mathcal N_v$ 。如果收集到的节点数量小于 $k$$k$ ，则使用最近添加到 ${\mathcal{N}}_v$$\mathcal N_v$ 节点的一阶邻域（即 BFS 过程），直到 ${\mathcal{N}}_v$$\mathcal N_v$ 中至少有 $k$$k$ 个节点；或者没有更多的邻居节点添加为止。注意，最终 ${\mathcal{N}}_v$$\mathcal N_v$ 的大小可能不等于 $k$$k$ 。

   即，广度优先搜索 $k$$k$ 个最近邻的节点（包括它自身）。

   另外，最终得到的 ${\mathcal{N}}_v$$\mathcal N_v$ 丢失了距离信息（和节点 $v$$v$ 的距离）。所以，如果这里能够保存距离信息，是否会更有利？

2. Neighborhood Assembly 算法：

   • 算法输入：当前节点 $v$$v$ ，感受野尺寸 $k$$k$

   • 算法输出：节点 $v$$v$ 的局部邻域 ${\mathcal{N}}_v$$\mathcal N_v$

   • 算法步骤：

     • 初始化：${\mathcal{N}}_v=[v],\mathcal{B}=[v]$$\mathcal N_v = [v], \mathcal B=[v]$ ，其中 $\mathcal{B}$$\mathcal B$ 存放BFS 遍历到的节点。

       注意，节点 $v$$v$ 也是它自身的邻居。

     • 迭代，直到 $|{\mathcal{N}}_v|\ge k$$|\mathcal N_v|\ge k$ 或者 $|\mathcal{B}|=0$$|\mathcal B|=0$ 停止迭代。迭代步骤：

       • 获取当前BFS 遍历节点的一阶邻域：$\mathcal{B}=\bigcup _{w\in \mathcal{B}}{\mathcal{N}}_w^{(1)}$$\mathcal B = \bigcup_{w\in \mathcal B}\mathcal N_w^{(1)}$，其中 ${\mathcal{N}}_w^{(1)}$$\mathcal N_w^{(1)}$ 表示节点 $w$$w$ 的一阶邻域集合。

       • 合并BFS 遍历到的节点：${\mathcal{N}}_v={\mathcal{N}}_v\bigcup \mathcal{B}$$\mathcal N_v = \mathcal N_v\bigcup \mathcal B$ 。

     • 返回 ${\mathcal{N}}_v$$\mathcal N_v$ 。

1.2.3 Graph Normalization

1. 子图归一化是对邻域子图的节点施加一个顺序，使得节点从无序的图空间映射到线性顺序的排序空间。子图归一化的基本思想是利用 graph labeling，对于不同子图中的节点，当且仅当节点在各自子图中的结构角色相似时，才给它们分配到各自邻接矩阵中的相似的相对位置（similar relative position）。

   为了形式化该思想，我们定义了一个 Optimal Graph Normalization 问题，该问题的目标是找到给定的图集合的最佳 labeling 。

2. Optimal Graph Normalization 问题：令 $\mathcal{G}$$\mathcal G$ 为一组图，每个图包含 $k$$k$ 个节点。令 $F_l(\cdot )$$F_l(\cdot)$ 为一个 graph labeling 过程。令 $d_G(\cdot ,\cdot )$$d_G(\cdot,\cdot)$ 为 $k$$k$ 节点图之间的距离函数，令 $d_A(\cdot ,\cdot )$$d_A(\cdot,\cdot)$ 为 $k\times k$$k\times k$ 矩阵之间的距离函数。则我们的目标是寻找 ${\hat{F}}_l(\cdot )$$\hat F_l(\cdot)$，使得：

   $${\hat{F}}_l=\arg \underset{F_l}{min}{\mathbb{E}}_{\mathcal{G}}\left[|d_A({\mathbf{A}}^l(G),{\mathbf{A}}^l(G^{\prime }))-d_G(G,G^{\prime })|\right]$$

   即：从 $\mathcal{G}$$\mathcal G$ 中随机均匀采样的两个子图，子图在排序空间（基于 $F_l$$F_l$ 得到的邻接矩阵）的距离与图空间的距离的差距最小。

   图的最优归一化问题是经典的图规范化问题（graph canonicalization problem）的推广。但是经典的labeling 算法仅针对同构图（isomorphic graph ）最佳，对于相似但是不同构的图可能效果不佳。相比之下，最优归一化问题的期望值越小，则labeling 过程将具有相似结构角色的节点进行对齐的效果越好。这里结构相似度由 $d_G(G,G^{\prime })$$d_G(G,G^\prime)$ 来衡量。

   • 关于图的最优归一化问题，这里给出了两个定理：

     • 定理一：图的最优归一化问题是 NP-hard 。

       证明：通过从子图同构进行规约（ reduction ）。

       PATCHY-SAN 无法完全解决图的最优归一化问题，它只是比较了不同的 graph labeling 方法，然后选择其中表现最好的那个。

     • 定理二：设 $\mathcal{G}$$\mathcal G$ 为一组图，令 $(G_1,G_1^{\prime }),\cdots ,(G_N,G_N^{\prime })$$(G_1,G_1^\prime),\cdots,(G_N,G_N^\prime)$ 是从 $\mathcal{G}$$\mathcal G$ 中独立随机均匀采样的一对图的序列。令：

       $$\begin{array}{c}{\hat{\theta }}_l=\frac{1}{N}\sum _{i=1}^N{d}_A({\mathbf{A}}^l(G_i),{\mathbf{A}}^l(G_i^{\prime }))\\ {\theta }_l={\mathbb{E}}_{\mathcal{G}}\left[|d_A({\mathbf{A}}^l(G),{\mathbf{A}}^l\left(G^{\prime }\right))-d_G(G,G^{\prime })|\right]\end{array}$$

       如果 $d_A({\mathbf{A}}^l(G),{\mathbf{A}}^l(G^{\prime }))\ge d_G(G,G^{\prime })$$d_A\left(\mathbf A^l(G),\mathbf A^l(G^\prime)\right) \ge d_G(G,G^\prime)$ ，则当且仅当 ${\theta }_{l_1}<{\theta }_{l_2}$$\theta_{l_1}\lt \theta_{l_2}$ 时有 ${\mathbb{E}}_{\mathcal{G}}\left[{\hat{\theta }}_{l_1}\right]<{\mathbb{E}}_{\mathcal{G}}\left[{\hat{\theta }}_{l_2}\right]$$\mathbb E_\mathcal G\left[\hat \theta_{l_1}\right]\lt \mathbb E_{\mathcal G}\left[\hat\theta_{l_2}\right]$ 。其中 $l_1,l_2$$l_1,l_2$ 表示采用不同的 graph labeling 。证明见论文。

       该定理使得我们通过比较估计量 ${\hat{\theta }}_l$$\hat\theta_l$ 来以无监督的方式比较不同的 graph labeling 。我们可以简单的选择使得 ${\hat{\theta }}_l$$\hat\theta_l$ 最小的graph labeling 。

       当我们在图上选择编辑距离（edit distance）、在矩阵 ${\mathbf{A}}^l(G)$$\mathbf A^l(G)$ 上选择汉明距离时，假设条件 $d_A\ge d_G$$d_A\ge d_G$ 成立。

       另外，上述结论不仅对无向图成立，对于有向图也成立。

3. 图的归一化问题，以及针对该问题的合适的graph labeling 方法是PATCHY-SAN 算法的核心。我们对节点 $v$$v$ 的邻域子图进行归一化，并约束节点的 label：任意两个其它节点 $u,w$$u,w$ ，如果 $d(u,v)<d(w,v)$$d(u,v) \lt d(w,v)$ 则 $F_r(u)<F_r(w)$$F_r(u) \lt F_r(w)$ ，即距离 $v$$v$ 越近，排名越靠前。该约束保证了节点 $v$$v$ 的排名总是1（即排名最靠前）。

   注意，PATCHY-SAN 中应用了两种 graph labeling 函数：

   • 第一种 graph labeling 函数 $F_l(\cdot )$$F_l(\cdot)$ ，用于选择节点序列，即 Select Node Sequence 算法。

   • 第二种 graph labeling 函数就是这里的距离函数，用于图的归一化问题，即 Graph Normalization 算法。

   由于大多数 labeling 方法不是单射的，因此有必要打破 same-label 节点之间的联系。为此，我们使用 NAUTY。NAUTY 接收先验的 node partition 作为输入，并通过选择字典顺序最大的邻接矩阵来打破剩余的联系（ remaining ties ）。

   注意，节点 $v$$v$ 的局部邻域 ${\mathcal{N}}_v$$\mathcal N_v$ 中，可能存在多个与节点 $v$$v$ 距离相等的邻居节点，因此距离函数作为 graph labeling 函数不是单射的。

   众所周知，对于有界degree 的图的同构问题可以在多项式时间求解，由于邻域子图的规模为 $k$$k$ 是一个常数，因此图的归一化算法可以在多项式时间内求解。我们的实验证明：图的邻域计算graph labeling 的过程仅产生一个微不足道的开销。

4. Graph Normalization 算法：

   • 算法输入：

     • 节点 $v$$v$ 及其局部邻域 ${\mathcal{N}}_v$$\mathcal N_v$

     • graph labeling 函数 $F_l^{{}^{\prime }}(\cdot )$$F_l^{^\prime}(\cdot)$（注意，它可能与 Select Node Sequence 算法中的 graph labeling 函数 $F_l(\cdot )$$F_l(\cdot)$ 有所不同）

     • 感受野尺寸 $k$$k$

   • 输出：归一化的邻域子图

   • 算法步骤：

     • 对 ${\mathcal{N}}_v$$\mathcal N_v$ 中的每个节点，使用 $F_l^{{}^{\prime }}(\cdot )$$F_l^{^\prime}(\cdot)$ 计算这些节点对 $v$$v$ 的排名，使得：

       $$\mathrm{\forall }u,w\in {\mathcal{N}}_v:d(u,v)<d(w,v)\to F_r(u)<F_r(w)$$

     • 如果 $|{\mathcal{N}}_v|>k$$|\mathcal N_v|\gt k$，则根据 ranking 取 ${\mathcal{N}}_v$$\mathcal N_v$ 中的 top k 个节点，对所选择的节点再执行一次labeling 以及 ranking 的过程。

       这里必须使用 $F_r(\cdot )$$F_r(\cdot)$ 在筛选出的较小的节点集合上重新计算，因为新的结构导致了新的 labeling 分布。

     • 如果 $|{\mathcal{N}}_v|<k$$|\mathcal N_v|\lt k$，则：添加 $k-|{\mathcal{N}}_v|$$k-|\mathcal N_v|$ 个断开的虚拟节点。

     • 根据这 $k$$k$ 个节点的排名来归一化这些节点，并返回归一化的结果。

5. 下图为对红色根节点 $v$$v$ 的邻域进行归一化过程，颜色表示到根节点的距离，感受野尺寸为 $k=9$$k=9$ 。首先利用graph labeling 对节点进行排序，然后创建归一化的邻域。

   归一化还包括裁剪多余的节点和填充虚拟节点。节点的不同属性对应于不同的输入通道。不仅可以针对节点创建感受野，还可以针对边创建感受野，边的感受野尺寸为 $k\times k$$k\times k$ ，边的不同属性对应不同的输入通道。

   正如前面的评论所说，最终得到的 ${\mathcal{N}}_v$$\mathcal N_v$ 丢失了距离信息（和节点 $v$$v$ 的距离）。那么这里是否可以新增一个 “距离通道”，这个距离通道保存距离属性，即邻居节点和根节点 $v$$v$ 的距离。

   或者，如后文所述，也可以直接采用边的感受野（尺寸为 $k\times k$$k\times k$ ）。

   

6. 创建感受野的 Create Receptive Field 算法：

   • 算法输入：节点 $v$$v$ ，$F_l^{\prime }(\cdot )$$F_l^\prime(\cdot)$ ，感受野大小 $k$$k$

   • 算法输出：节点 $v$$v$ 的感受野

   • 算法步骤：

     • 计算节点 $v$$v$ 的邻域：${\mathcal{N}}_v=\text{NeighborhoodAssembly}(v,k)$$\mathcal N_v=\text{NeighborhoodAssembly}(v,k)$ 。

     • 归一化邻域子图：$G_{norm}=\text{GraphNormalization}({\mathcal{N}}_v,v,F_l,k)$$G_{norm} = \text{GraphNormalization}(\mathcal N_v,v,F_l,k)$。

     • 返回 $G_{norm}$$G_{norm}$。

7. 我们可以将 PATCHY-SAN 与图像的 CNN 相关联。

   定理：在图像中得到的一个像素序列上应用 PATCHY-SAN ，其中感受野尺寸为 $k=(2b-1{)}^2$$k=(2b-1)^2$、步幅为 $s$$s$ 、非零填充以及采用 1-WL 归一化，则这等效于 CNN 的一个感受野大小为 $2b-1$$2b-1$、步幅为 $s$$s$ 、非零填充的卷积层。

   证明：如果输入图为一个正方形网格，则为节点构造的 1-WL 归一化的感受野始终是具有唯一节点顺序的正方形网格。

1.2.4 PATCHY-SAN 架构

1. PATCHY-SAN 既能处理节点，也能处理边；它既能处理离散属性，也能处理连续属性。

2. PATCHY-SAN 对每个输入图 $G$$G$ 产生 $w$$w$ 个尺寸为 $k$$k$ 的归一化的感受野。假设 $a_v$$a_v$ 为节点属性的数量、$a_e$$a_e$ 为边属性的数量，则这将产生一个 $w\times k\times a_v$$w\times k\times a_v$ 的张量（节点的感受野）以及一个 $w\times k\times k\times a_e$$w\times k\times k \times a_e$ 的张量（边的感受野）。这里 $a_v$$a_v$ 和 $a_e$$a_e$ 都是输入通道的数量。

   我们可以将这两个张量reshape 为一个 $wk\times a_v$$wk\times a_v$ 的张量和一个 $w{k}^2\times a_e$$wk^2\times a_e$ 的张量，然后对每个输入通道采用一个一维卷积层进行卷积。节点产生的张量应用步幅 $k$$k$ 、感受野尺寸 $k$$k$ 的一维卷积层，边产生的张量应用步幅 $k^2$$k^2$、 感受野尺寸 $k^2$$k^2$ 的一维卷积层 。剩下的结构可以任意结合 CNN 的组件。另外我们可以利用融合层来融合来自节点的卷积输出feature map 和来自边的卷积输出 feature map 。

1.2.5 算法复杂度

1. PATCHY-SAN 的创建感受野算法非常高效。另外，由于这些感受野的生成是相互独立的，因此感受野生成过程原生支持并行化。

2. 定理：令 $N$$N$ 为数据集中图的数量，$k$$k$ 为感受野尺寸，$w$$w$ 为宽度（每个子图包含的感受野数量）。假设 $O(f_l(n,m))$$O(f_l(n,m))$ 为包含 $n$$n$ 个节点、$m$$m$ 条边的图的 graph labeling 过程的计算复杂度。则PATCHY-SAN 最坏情况下的计算复杂度为 $O(N\times w\times [f_l(n,m)+n\log n+\exp (k)])$$O(N\times w\times [f_l(n,m)+n\log n +\exp(k)])$ 。

   证明见论文。

   当采用Weisfeiler-Lehman 算法作为graph labeling 算法时，它的算法复杂度为 $O((n+m)\log n)$$O((n+m)\log n)$ 。考虑到 $w\ll n,k\ll n$$w\ll n,k \ll n$ ，则PATCHY-SAN 的复杂度为 $N$$N$ 的线性、$m$$m$ 的准线性、$n$$n$ 的准线性。

1.3 实验

1.3.1 运行时分析

1. 我们通过将PATCHY-SAN 应用于实际的图来评估其计算效率，评估指标为感受野的生成速度。我们将 PATCHY-SAN 生成感受野的速度，与 STOA 的 CNN 执行学习的速度进行比较。

2. 数据集：所有输入图都来自 Python 模块 GRAPHTOOL 。

   • torus 图：具有10k 个节点的周期性晶格。

   • random 图：具有10 个节点的随机无向图，节点的度的分布满足：$p(k)\propto 1/k$$p(k)\propto 1/k$ ，以及 $k_{max}=3$$k_{\max}=3$ 。

   • power 图：美国电网拓扑网络。

   • polbooks：2004年美国总统大选期间出版的有关美国政治书籍的 co-purchasing 网络。

   • preferential：一个 preferential attachment network，其中最新添加的节点的degree 为 3 。

   • astro-ph：天体物理学 arxiv 上作者之间的 co-authorship 网络。

   • email-enron：一个由大约 50万 封已发送 email 生成的通信网络。

3. 我们的PATCHY-SAN 采用 1-dimensional Weisfeiler-Lehman:1-WL 算法来归一化邻域子图。下图给出了每个输入图每秒产生感受野的速度。所有实验都是在单台 2.8 GHZ GPU、64G 内存的机器上执行。

   • 对于感受野尺寸 $k=5/k=10$$k=5/k=10$ ，除了在 email-eron 上的速度为 600/s 和 320/s 之外，在其它所有图上PATCHY-SAN 创建感受野的速度超过 1000/s 。

   • 对于最大的感受野尺寸 $k=50$$k=50$ ，PATCHY-SAN 创建感受野的速度至少为 100/s 。

   对于一个经典的带两层卷积层、两层 dense 层的 CNN 网络，我们在相同机器上训练速度大概是 200-400 个样本/秒，因此PATCHY-SAN 感受野的生成速度足以使得下游 CNN 组件饱和。

   

1.3.2 可视化

1. 可视化实验的目的是定性研究 restricted boltzman machine: RBM 等流行模型是否可以与 PATCHY-SAN 结合从而用于无监督特征学习。我们将 PATCHY-SAN 学到的尺寸为9 的归一化感受野使用 restricted boltzman machine:RBM 进行无监督学习，RNM 所学到的特征对应于重复出现的感受野模式。其中：

   • PATCHY-SAN 采用 1-WL 算法进行邻域子图归一化。

   • 采用单层RBM ，隐层包含 100 个隐单元。

   • RBM 采用对比散度算法（contrastive divergence: CD）训练 30 个 epoch，学习率设为 0.01 。

   下图给出了从四张图中得到的样本和特征。我们将RBM 学到的特征权重可视化（像素颜色越深，则对应权重重大）。另外我们还采样了每种模式对应的三个节点的归一化邻域子图，黄色节点表示当且节点（排序为1）。

   左上角为 torus 周期性晶格图、左下角为 preferential attachment 图、右上角为 co-purchasing 图、右下角为随机图。

   

1.3.3 图的分类

1. 图分类任务是将每个图划分到若干类别之一。我们采用6 个标准 benchmark 数据集来比较不同图分类模型的分类准确性和运行时间。

   • MUTAG 数据集：由188 种硝基化合物组成的数据集，其类别表明该化合物是否对细菌具有诱变 （mutagenic ）作用。

   • PTC 数据集：由 344 种化合物组成的数据集，其类别表明是否对老鼠具有致癌性。

   • NCI1 和 NCI109 数据集：筛选出的抑制 non-small 肺癌细胞和卵巢癌细胞活性的化合物。

   • PROTEIN：一个图的数据集，其中图的节点表示次级结构元素（ secondary structure element）， 边表示氨基酸序列中的相邻关系，或者三维空间中的氨基酸相邻关系。其类别表示酶或者非酶。

   • D&D：由 1178 种蛋白质组成的数据集，其类别表明是酶还是非酶。

2. 我们将PATCHY-SAN 和一组核方法比较，包括shortest-path kernel: SP 、random walk kernel: RW、graphlet count kernel: GK，以及 Weisfeiler-Lehman sbutree kernel: WL 。

   • 对于核方法，我们使用 LIB-SVM 模型来训练和评估核方法的效果。我们使用10 折交叉验证，其中9-fold 用于训练，1-fold 用于测试。我们重复10 次并报告平均准确率和标准差。

     类似之前的工作，我们设置核方法的超参数为：WL 的高度参数设置为2 ，GK 的尺寸参数设置为 7 ，RW 的衰减因子从 $\{{10}^{-6},{10}^{-5},\cdots ,{10}^{-1}\}$$\{10^{-6},10^{-5},\cdots,10^{-1}\}$ 中进行挑选。

   • 对于 PATCHY-SAN: PSCN 方法，我们使用 1-dimensional WL 归一化，设置 $w$$w$ 为平均节点数量，设置感受野尺寸分别为 $k=5$$k=5$ 和 $k=10$$k=10$ 。实验中我们仅使用节点的属性，但是在 $k=10$$k=10$ 时我们实验了融合节点的感受野和边的感受野，记作 $k={10}^E$$k=10^E$ 。

     所有 PSCN 都使用了具有两个卷积层、一个dense 层、一个 softmax 层的网络结构。其中：

     • 第一个卷积层有 16 个输出通道，第二个卷积层有 8 个输出通道，步长 $s=1$$s=1$，感受野大小为 $k=10$$k=10$ 。

     • dense 层有 128 个隐单元（relu 激活函数），采用dropout = 0.5 的 dropout。我们采用一个较小的隐单元数量以及 dropout 从而避免模型在小数据集上过拟合。

     所有卷积层和 dense 层的激活函数都是 reLU 。 模型的优化算法为 RMSPROP 优化算法，并基于Keras 封装的 Theno 实现。

     所有 PSCN 需要优化的超参数为 epoch 数量以及 batch-size 。

     当 $k=10$$k=10$ 时，我们也对 PATCHY-SAN 抽取的感受野应用一个逻辑回归分类器 PSLR 。

3. 实验结果：这些模型在 benchmark 数据集上的结果如下表所示。其中前三行给出了各数据集的属性，包括图的最大节点数Max、图的平均节点数Avg、图的数量Graphs 。我们忽略了 NCI109 的结果，因为它几乎和 NCI1 相同。

   • 尽管使用了非常普通的CNN 架构，PSCN 的准确率相比现有的graph kernel 方法具有很强的竞争力。在大多数情况下，采用 $k=10$$k=10$ 的 PSCN 具有最佳的分类准确性。

   • PSCN 这里的预测方差较大，这是因为：benchmark 数据集较小，另外 CNN 的一些超参数（epoch 和 batch-size 除外）没有针对具体的数据集进行优化。与图像和文本数据的体验类似，我们预期 PATCHY-SAN 在大型数据集上的表现更好。

   • PATCHY-SAN 的运行效率是graph kernel 中最高效的 WL 方法的 2到 8 倍。我们预计具有大量 graph 的数据集上，PATCHY-SAN 的性能优势会更加明显。

   • PATCHY-SAN + 逻辑回归的效果较差，这表明 PATCHY-SAN 更适合搭配 CNN 。CNN 学到了归一化感受野的非线性特征组合，并在不同感受野之间共享权重。

   • 采用中介中心性归一化（ betweeness centrality normalization ）结果也类似（未在表中体现），除了它的运行时间大约增加了 10% 。

   融合节点的感受野和边的感受野的 $\text{PSCN }k={10}^E$$\text{PSCN } k =10^E$ 的效果优于 PSCN k=10，这表明保留邻域子图的距离信息的有效性。

   

4. 我们在较大的社交网络图数据集上使用相同的配置进行实验，其中每个数据集最多包含 12k 个图，每个图平均 400 个节点。我们将 PATCHY-SAN 和之前报告的 graphlet count: GK、deep graplet count kernel: DGK 结果相比。

   我们使用归一化的节点degree 作为节点的属性，这突出了PATCHY-SAN 的优势之一：很容易地包含连续特征。

   可以看到 PSCN 在六个数据集的四个中明显优于其它两个核方法，并且在剩下两个数据集也取得了很好的性能。